package com.bm.constant;

import java.util.*;

/**
 * @author 86134
 * @version 1.0
 * @description TODO
 * @date 2024/2/28 16:50
 */

public class Test {
    public static final int MOD = 998244353;
    static String s = "abcdefghijklnopqr";
    static char[] arr = s.toCharArray();
    static Map<Character, Integer> map;

    public static void main(String[] args) {

        //排列距离
// 1:无需package
// 2: 类名必须Main, 不可修改
//                Scanner scan = new Scanner(System.in);
//                map = new HashMap<>();
//                for(int i = 0; i < arr.length; i++) {
//                    map.put(arr[i], i);
//                }
//                char[] s1 = "aejcldbhpiogfqnkr".toCharArray();
//                char[] s2 = "ncfjboqiealhkrpgd".toCharArray();
//                System.out.print(Math.min(kongrtuo(s2) - kongrtuo(s1), doFactorial(17) - kongrtuo(s2) + kongrtuo(s1)));
//                scan.close();
//        map = new HashMap<>();
//        for (int i = 0; i < arr.length; i++) {
//            map.put(arr[i], i);
//        }
//        char[] s1 = "aejcldbhpiogfqnkr".toCharArray();
//        char[] s2 = "ncfjboqiealhkrpgd".toCharArray();
//        System.out.print(Math.min(kongrtuo(s2) - kongrtuo(s1), doFactorial(17) - kongrtuo(s2) + kongrtuo(s1)));
        subsetsWithDup(new int[]{1,2,2});
    }

    public static List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        Set<List<Integer>> ans = new HashSet<>();
        List<Integer> cur = new ArrayList<>();
        dfs(nums, 0, cur, ans);
        return new ArrayList<>(ans);
    }

    void dfs2(int[] nums ,int u,List<Integer> cur,Set<List<Integer>> ans){
        //出口
        if(u == nums.length){
            ans.add(cur);
            return;
        }
        cur.add(nums[u]);
        dfs2(nums,u+1,cur,ans);
        //删除最后一个
        cur.remove(cur.size() - 1);
        dfs2(nums,u+1,cur,ans);
    }

    /**
     * @param nums 原输入数组
     * @param u 当前决策到原输入数组中的哪一位
     * @param cur 当前方案
     * @param ans 最终结果集
     */
    static void dfs(int[] nums, int u, List<Integer> cur, Set<List<Integer>> ans) {
        // 所有位置都决策完成，将当前方案放入结果集
        if (nums.length == u) {
            ans.add(new ArrayList<>(cur));
            return;
        }

        // 选择当前位置的元素，往下决策
        cur.add(nums[u]);
        dfs(nums, u + 1, cur, ans);

        // 不选当前位置的元素（回溯），往下决策
        cur.remove(cur.size() - 1);
        dfs(nums, u + 1, cur, ans);
    }




    public static long kongrtuo(char[] s) {
        long ans = 0;
        boolean[] visited = new boolean[s.length];
        for (int i = 0; i < s.length; i++) {
            int j = map.get(s[i]);
            int k = 0;
            for (int l = 0; l < j; l++) {
                if (!visited[l]) {
                    k++;
                }
            }
            ans += k * doFactorial(s.length - i - 1);
            visited[j] = true;
        }
        return ans;
    }

    public boolean exist2(char[][] board, String word) {
        char[] words = word.toCharArray();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (dfs2(board, words, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean dfs2(char[][] board, char[] word, int i, int j, int k) {
        if (i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[k]) {
            return false;
        }
        if (k >= word.length) {
            return true;
        }
        board[i][j] = '\0';
        boolean res = dfs2(board, word, i + 1, j, k + 1) || dfs2(board, word, i - 1, j, k + 1) ||
                dfs2(board, word, i, j + 1, k + 1) || dfs2(board, word, i, j - 1, k + 1);
        board[i][j] = word[k];
        return res;
    }


    public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (dfs(board, words, i, j, 0)) return true;
            }
        }
        return false;
    }

    public boolean dfs(char[][] board, char[] words, int i, int j, int k) {
        if (i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != words[k]) {
            return false;
        }
        if (k == words.length - 1) {
            return true;
        }
        board[i][j] = '\0';
//        if(dfs(board,words,i+1,j,k+1) || dfs(board,words,i-1,j,k+1)||
//        dfs(board,words,i,j+1,k+1) || dfs(board,words,i,j-1,k+1)){
//
//        }
        boolean res = dfs(board, words, i + 1, j, k + 1) || dfs(board, words, i - 1, j, k + 1) ||
                dfs(board, words, i, j + 1, k + 1) || dfs(board, words, i, j - 1, k + 1);
        board[i][j] = words[k];
        return res;

    }


    public static long doFactorial(long n) {
        long ans = 1;
        for (long i = 1; i <= n; i++) {
            ans *= i;
        }
        return ans;
    }

//            public static long kongrtuo(char[] s) {
//                long ans = 0;
//                boolean[] visited = new boolean[s.length];
//                for(int i = 0; i < s.length; i++) {
//                    int j = map.get(s[i]);
//                    int k = 0;
//                    for(int l = 0; l < j; l++) {
//                        if(!visited[l]) k++;
//                    }
//
//                    // k = 当前的我位数
//                    // s.length - 1 - i 我后面还有几个数
//                    ans += k * doFactorial(s.length - 1 - i);
//                    visited[j] = true;
//                }
//                return ans;
//            }
//
//            public static long doFactorial(int n) {
//                long ans = 1;
//                for(int i = 1; i <= n; i++) {
//                    ans *= i;
//                }
//                return ans;
//            }


    // 分糖果
//
//        Scanner scanner = new Scanner(System.in);
//        int n = scanner.nextInt();
//        int x = scanner.nextInt();
//        char[] chars = scanner.next().toCharArray();
//        //排序在字典序里最小的里面找到最大的
//        Arrays.sort(chars);
//        //第一种情况 aaaaa
//        if(chars[0] == chars[n - 1]){
//            int count = n / x + (n % x == 0 ? 0 : 1);
//            for (int i = 0; i < count; i++) {
//                System.out.print(chars[i]);
//            }
//            //简单理解为第一位都相等   aaabbcd
//        }else if(chars[0] == chars[x - 1]){
//            for (int i = x - 1; i < n; i++) {
//                System.out.print(chars[i]);
//            }
//            // aabcd
//        }else{
//            System.out.println(chars[x - 1]);
//        }


//        Scanner sc = new Scanner(System.in);
//        long a = sc.nextLong();
//        long b = sc.nextLong();
//
//        long res = a , x = a;
//
//        for (int i = 2; i <= Math.sqrt(x) ; i++) {
//            if(x % i == 0){
//                while (x % i == 0){
//                    x /= i;
//                }
//                res = res / i * (i - 1);
//            }
//        }
//        if(x > 1){
//            res = res / x * (x - 1);
//        }
//        System.out.println(res * qmi(a,b-1) % MOD);


//        Date date = new Date();
//        System.out.println(DateTime.now().toDateStr().replaceAll("-", ""));
//        String dateStr =  date.getYear()+""+date.getMonth()+""+date.getDay();

//        System.out.println(DigestUtils.md5DigestAsHex("123456".getBytes()));
//        queenNine();
//        int i = 1;
//        int ans = 0;
//        while (true){
//            if(check(i,2) && check(i,8) && check(i,10) && check(i,16)){
//                ans++;
//            }
//            if(ans == 2023){
//                System.out.println(i);
//                return;
//            }
//            i++;
//        }


    public static long qmi(long a, long b) {
        long res = 1;
        while (b > 0) {
            if (b % 2 != 0) {
                res = res * a % MOD;
            }
            a = a * a % MOD;
            b >>= 1;
        }
        return res;
    }


    public static boolean check(int x, int i) {
        int n = x;
        int ans = 0;
        while (x > 0) {
            ans += x % i;
            x /= i;
        }
        return n % ans == 0;
    }

    public static void queenNine() {
        long sum = 0;
        for (int i = 1; i < 40; i++) {
            long tamp = 1;
            for (int j = 1; j <= i; j++) {
                tamp *= j;
                tamp %= 1000000000l;
            }
            sum += tamp;
        }
        System.out.println(sum % 1000000000l);
    }
}
